package com.fan.leetcode;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 981. 基于时间的键值存储
 *
 * @author ZhangFan
 * @since 2021/8/3 下午 10:28
 */
public class Question981 {
    @Test
    public void test981() {
        TimeMap obj = new TimeMap();
        obj.set("foo", "bar", 1);
        System.out.println(obj.get("foo", 1));
        System.out.println(obj.get("foo", 3));
    }

    class Entry {
        private Integer key;
        private String value;

        public Entry(Integer key, String value) {
            this.key = key;
            this.value = value;
        }

        public Integer getKey() {
            return key;
        }

        public void setKey(Integer key) {
            this.key = key;
        }

        public String getValue() {
            return value;
        }

        public void setValue(String value) {
            this.value = value;
        }
    }

    class TimeMap {
        private Map<String, List<Entry>> map;

        /**
         * Initialize your data structure here.
         */
        public TimeMap() {
            map = new HashMap<>();
        }

        public void set(String key, String value, int timestamp) {
            List<Entry> timeList = map.getOrDefault(key, new ArrayList<>());
            timeList.add(new Entry(timestamp, value));
            map.put(key, timeList);
        }

        public String get(String key, int timestamp) {
            List<Entry> timeList = map.get(key);
            if (timeList == null) {
                return "";
            }
            int start = 0, end = timeList.size() - 1;
            if (timeList.get(start).getKey() > timestamp) {
                return "";
            }
            if (timeList.get(end).getKey() < timestamp) {
                return timeList.get(end).getValue();
            }
            while (start <= end) {
                int middle = (start + end) / 2;
                Integer temp = timeList.get(middle).getKey();
                if (temp == timestamp) {
                    return timeList.get(middle).getValue();
                }
                if (timestamp > temp) {
                    start = middle + 1;
                }
                if (timestamp < temp) {
                    end = middle - 1;
                }
            }
            return timeList.get(end).getValue();
        }
    }
}
